#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>

// 编译时 gcc -std=c99 bin_tree_array.c -lm

#define TYPE int
#define NIL	 0

typedef struct BinTree
{
	TYPE* arr;
	size_t cal;
}BinTree;

// 创建
BinTree* creat_tree(size_t cal);
// 初始化
void init_tree(BinTree* tree,TYPE* arr,size_t len);
// 前序遍历
void prev_show(BinTree* tree);
// 中序遍历
void in_show(BinTree* tree);
// 后序遍历
void post_show(BinTree* tree);
// 左子结点
TYPE* lchild_tree(BinTree* tree,TYPE data);
// 右子结点
TYPE* rchild_tree(BinTree* tree,TYPE data);
// 左兄弟
TYPE* lbrother_tree(BinTree* tree,TYPE data);
// 右兄弟
TYPE* rbrother_tree(BinTree* tree,TYPE data);
// 父结点
TYPE* parent_tree(BinTree* tree,TYPE data);
// 访问
TYPE* access_tree(BinTree* tree,size_t level,size_t order);
// 层序
void level_order_show(BinTree* tree);
// 高度
size_t high_tree(BinTree* tree);

int main()
{
	TYPE arr[] = {1,2,3,4,5,6,7,8};
	BinTree* tree = creat_tree(256);
	init_tree(tree,arr,8);
	printf("%d\n",high_tree(tree));
	level_order_show(tree);
}

// 创建
BinTree* creat_tree(size_t cal)
{
	BinTree* tree = malloc(sizeof(BinTree));
	tree->arr = calloc(cal,sizeof(TYPE));
	tree->cal = cal;
	return tree;
}

// 初始化
void init_tree(BinTree* tree,TYPE* arr,size_t len)
{
	memcpy(tree->arr,arr,sizeof(TYPE)*len);
}

void _prev_show(BinTree* tree,size_t i)
{
	printf("%d ",tree->arr[i]);
	
	if(NIL != tree->arr[i*2+1])
		_prev_show(tree,i*2+1);
		
	if(NIL != tree->arr[i*2+2])
		_prev_show(tree,i*2+2);
}

// 前序遍历
void prev_show(BinTree* tree)
{
	_prev_show(tree,0);
	printf("\n");
}

void _in_show(BinTree* tree,size_t i)
{
	if(NIL != tree->arr[i*2+1])
		_in_show(tree,i*2+1);
		
	printf("%d ",tree->arr[i]);
	
	if(NIL != tree->arr[i*2+2])
		_in_show(tree,i*2+2);
}

// 中序遍历
void in_show(BinTree* tree)
{
	_in_show(tree,0);
	printf("\n");
}

void _post_show(BinTree* tree,size_t i)
{
	if(NIL != tree->arr[i*2+1])
		_post_show(tree,i*2+1);
	if(NIL != tree->arr[i*2+2])
		_post_show(tree,i*2+2);
	printf("%d ",tree->arr[i]);
}
// 后序遍历
void post_show(BinTree* tree)
{
	_post_show(tree,0);
	printf("\n");
}

// 左子结点
TYPE* lchild_tree(BinTree* tree,TYPE data)
{
	for(int i=0; i<tree->cal; i++)
	{
		if(tree->arr[i]==data && NIL!=tree->arr[i*2+1])
		{
			return tree->arr+i*2+1;
		}
	}

	return NULL;
}

// 右子结点
TYPE* rchild_tree(BinTree* tree,TYPE data)
{
	for(int i=0; i<tree->cal; i++)
	{
		if(tree->arr[i]==data && NIL!=tree->arr[i*2+2])
		{
			return tree->arr+i*2+2;
		}
	}
	return NULL;
}

// 左兄弟
TYPE* lbrother_tree(BinTree* tree,TYPE data)
{
	if(tree->arr[0] == data) return NULL;
	// 该结点必须是右子结点，下村必须是偶数
	for(int i=0; i<tree->cal; i++)
	{
		if(tree->arr[i] == data && 0==i%2)
		{
			return tree->arr+i-1;
		}
	}
	return NULL;
}

// 右兄弟
TYPE* rbrother_tree(BinTree* tree,TYPE data)
{
	if(tree->arr[0] == data) return NULL;
	for(int i=0; i<tree->cal; i++)
	{
		if(tree->arr[i] == data && i%2)
		{
			return tree->arr+i+1;
		}
	}

	return NULL;
}

// 父结点
TYPE* parent_tree(BinTree* tree,TYPE data)
{
	if(tree->arr[0] == data) return NULL;

	for(int i=0; i<tree->cal; i++)
	{
		if(tree->arr[i] == data && tree->arr[(i-1)/2])
		{
			return tree->arr+(i-1)/2;
		}
	}

	return NULL;
}

// 访问
TYPE* access_tree(BinTree* tree,size_t level,size_t order)
{
	if(pow(2,level-1) < order) return NULL;
	size_t i = pow(2,level-1)+order-2;
	if(i > tree->cal) return NULL;

	return tree->arr+i;
}

// 高度
size_t high_tree(BinTree* tree)
{
	size_t i=tree->cal;
	while(NIL == tree->arr[--i]);

	printf("%d %d\n",i,tree->arr[i]);
	size_t high = 0;
	do{
		high++;
	}while(pow(2,high)-2 < i);

	return high;
}

// 层序
void level_order_show(BinTree* tree)
{
	size_t h = high_tree(tree);
	printf("high:%d\n",h);
	for(int i=1; i<=h; i++)
	{
		printf("第%d行：",i);
		for(int j=1; j<=pow(2,i-1); j++)
		{
			printf("%d ",*access_tree(tree,i,j));
		}
		printf("\n");
	}
}
